import math
from direct import *
import numpy as np


def astart(maze, start, end,canPass = lambda maze,x,y:maze[x][y]!=0):
    rows, cols = maze.shape
    open_set = {start}
    close_set = set()
    path = [[(-1, -1) for i in range(cols)] for j in range(rows)]
    f = lambda x: math.fabs(end[0] - x[0]) + math.fabs(end[1] - x[1])
    while open_set:
        current = min(open_set, key=f)
        x, y = current
        if (current == end):
            while path[x][y]!=(-1,-1):
                # print(x,y)
                x,y=path[x][y]
            # for i in range(len(mazeData)):
            #     for j in range(len(mazeData[i])):
            #         print(mazeData[i][j],end=' ')
            #     print()

        open_set.remove(current)
        close_set.add(current)
        for dx, dy in DIRECTS :
            new_x, new_y = x + dx, y + dy
            next = (new_x,new_y)
            dr = get_direct_index((dx,dy))
            if 0 <= new_x < rows and 0 <= new_y < cols and canPass(maze,new_x,new_y) and next not in close_set:
                if next not in open_set:
                    path[new_x][new_y] = (x, y)
                    open_set.add((new_x,new_y))




def generate_maze(rows, cols, start, end):
    maze = np.zeros((rows, cols), dtype=int)  # 0表示墙
    stack = [start]  # 栈存储待访问的方块
    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]  # 定义四个方向
    while stack:
        current = stack.pop()
        x, y = current
        maze[x][y] = 1  # 标记为访问过的方块
        neighbors = []
        for dx, dy in directions:
            new_x, new_y = x + dx, y + dy
            if 0 <= new_x < rows and 0 <= new_y < cols and maze[new_x][new_y] == 0:
                neighbors.append((new_x, new_y))
        if neighbors:
            stack.append(current)  # 当前方块重新压入栈
            next_block = neighbors[np.random.randint(len(neighbors))]  # 随机选择下一个方块
            if next_block == end:
                maze[next_block[0]][next_block[1]] = 1
                break
            stack.append(next_block)
    return maze


if __name__ == "__main__":
    maze = generate_maze(10, 10, (0, 0), (9, 9))
    astart(maze,(0,0),(9,9))